1. Field of the Invention
This invention relates generally to electronic switches and more specifically to one-sided crosspoint switches for computer networks.
2. Description of the Prior Art
Crosspoint switches are used in the telephone and computer industry for switching data among communication lines. One type of crosspoint switch is the one-sided crosspoint switch described by Christos Georgiou in U.S. Pat. No. 4,635,250. FIG. 1 illustrates a prior art one-sided crosspoint switch. A set of data lines 101-116 is intersected by a set of internal buses 201-208, which together form a switching matrix. A crosspoint switching element (or "crosspoint") is located at each point of intersection. There are 128 crosspoint switching elements in the matrix illustrated in FIG. 1. Each data line also is connected to a switch port (or "port") via a port adapter. A connection between two data lines (and therefore between two ports) is set up by selecting one of the internal buses and then turning on the crosspoint switching elements at the points of intersection of the selected bus with each of the data lines. For example, a connection between data lines 104 and 112 (and therefore between the port connected to data line 104 and the port connected to data line 112) can be achieved by turning on switching elements 10 and 12, thereby making use of the bus 206. The same connection can be set up through any of the other internal buses, provided that it is not already in use for interconnecting a different pair of ports. For allowing simultaneous pairwise connections between all of the ports, the number of buses should be at least half the total number of ports. Such a switching system is called a non-blocking switch because it allows no connection to be blocked as a result of other connections. The 16-port switch in FIG. 1 is thus non-blocking because of the presence of eight internal buses.
A one-sided crosspoint matrix generally is constructed from one or more switching chips. If the number of ports in the system is small, the entire matrix can be implemented by means of a single chip. However, if the number of ports is large, it is necessary to partition the matrix into rectangular blocks so that each block can be implemented by a switching chip of moderate size. Each rectangular block or partition actually is a smaller one-sided crosspoint switch by itself. In such a case, the one-sided crosspoint switch can be thought of as consisting of a plurality of component one-sided crosspoint switches, typically arranged in rows and columns. For illustration, the switching matrix in FIG. 1 has been shown as consisting of four switching chips, each chip having eight horizontal data lines and four vertical internal buses.
A major advantage of one-sided crosspoint switches is the flexibility in allowing any of the internal buses to make a connection as long as the selected bus is not in use for another connection. This allows the system to operate in the presence of faulty buses. A faulty bus reduces the capacity by reducing the number of connections that can be provided simultaneously, but no ports are taken out of service as a result of the elimination of a faulty bus.
The switching gates of the crosspoint matrix are controlled by a controller 14 through a control bus 16 as shown in FIG. 1. Controller 14 receives requests for connection and disconnection from the port adapters over a port adapter bus 18 and activates or deactivates proper crosspoints in the matrix. When the combined rate at which such connections and disconnections are requested is high, a fast controller is required to handle these requests. This is frequently the case when the switch is used to interconnect computers in a multiprocessor system where the lifetime of a connection is very short.
A controller for control of one-sided crosspoint networks is described in U.S. Pat. No. 4,630,045 issued to Christos Georgiou. This controller achieves its speed by means of pipelining, that is by allowing one processing-step of a request to be executed simultaneously with another step of a second request.
When the number of ports in the switching matrix is large, however, the single controller approach described in U.S. Pat. No. 4,630,045 suffers from two limitations. If requests for connection or disconnection arrive simultaneously or close together at several ports, some of them will experience long service-times because a controller is capable of servicing requests at a rate which at best is only one per cycle, even with pipelining. Furthermore, a fault in the controller itself will disrupt its operation, thereby causing the entire system to be inoperational. In other words, the controller is a single point at which total failure can occur. The controller can be made fault-tolerant by replication, but this does not provide any improvement in performance during normal operation.
The present invention overcomes these two problems in part by distributing the control of the switching matrix among multiple controllers instead of using a single controller.
Distributed control of a two-sided crosspoint switch is described in U.S. Pat. No. 3,226,688 issued to Amdahl et al. In a two-sided crosspoint network, only one switching path exists between a pair of ports to be connected and not all pairs of ports can be connected together. Amdahl describes a modular computer system with a set of controlling modules and a set of controlled modules connected to each other through a two-sided crosspoint switch. A set of sense units controls the crosspoints, thereby allowing more than one request to be processed in the same cycle. However, every request is pre-assigned to a distinct controller, so failure of a controller affects those requests. Furthermore, the described technique cannot be applied to one-sided crosspoint networks where a multiplicity of paths exists for making a connection and any pair of ports can be connected together.